package com.xzz.dp;

import java.util.Arrays;

/**
 * @author: hhz
 * @create: 2021-12-30 15:03
 *712. 两个字符串的最小ASCII删除和
 *给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
 * 输入: s1 = "sea", s2 = "eat"
 * 输出: 231
 * 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
 * 在 "eat" 中删除 "t" 并将 116 加入总和。
 * 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
 *
 * 定义：将 s1[i..] 和 s2[j..] 删除成相同字符串，
 * 最小的 ASCII 码之和为 dp(s1, i, s2, j)。
 **/
public class MinimumDeleteSum {
    public static void main(String[] args) {
        System.out.println(minimumDeleteSum("delete","leet"));
    }

    static int[][] memo;
    public static int minimumDeleteSum(String s1, String s2) {
        memo = new int[s1.length()][s2.length()];
        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i],-1);
        }
        return dp(s1,0,s2,0);
    }
    public static int dp(String s1,int i, String s2,int j) {
        int res = 0;
        if(s1.length()==i){
            for (; j < s2.length(); j++) {
                res+=s2.charAt(j);
            }
            return res;
        }
        if(s2.length()==j){
            for (; i < s1.length(); i++) {
                res+=s1.charAt(i);
            }
            return res;
        }
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
        if(s1.charAt(i)==s2.charAt(j)){
            memo[i][j] = dp(s1,i+1,s2,j+1);
        }else {
            memo[i][j] = Math.min(
                    dp(s1,i+1,s2,j)+s1.charAt(i),
                    dp(s1,i,s2,j+1)+s2.charAt(j)
            );
        }
        return memo[i][j];
    }
}
